package algorithm.tree;

import algorithm.model.TreeNode;

import java.util.LinkedList;
import java.util.Deque;

/**
 * https://leetcode.com/problems/minimum-depth-of-binary-tree/
 * Easy
 * 树的最短高度.
 * 可以用深度优先，也可以用广度优先。
 *
 * 深度优先：需要遍历所有叶子节点的高度，找最短
 * 广度优先：找到的第一个叶子就是最短的
 * Created by yzy on 2021-03-16 20:26
 */
public class MinDepthTree {

    public static void main(String[] args) {
        TreeNode root = TreeNode.getTreeNode(new Integer[]{3,9,20,null,null,15,7});
        System.out.println(minDepth(root));
    }

    /**
     * 广度优先遍历。广度优先的实现方式可以用List，但是频繁的创建List会增加开销
     * 所以这里优化为使用双端队列
     * 0ms, 100%
     * 59.3MB, 78.84%
     * @param root
     * @return
     */
    public static int minDepth(TreeNode root) {
        if(root==null) return 0;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.addFirst(root);
        int currSize = 1;
        int nextSize = 0;
        int minDepth = 1;
        while(!list.isEmpty() && currSize>0){
            TreeNode node = list.pollLast();
            currSize--;
            if(node.left == null && node.right == null){
                return minDepth;
            }
            if(node.left != null){
                nextSize++;
                list.addFirst(node.left);
            }
            if(node.right != null){
                nextSize++;
                list.addFirst(node.right);
            }
            if(currSize==0){
                currSize=nextSize;
                nextSize=0;
                minDepth++;
            }
        }
        return 0;
    }

}
